package com.zwj.interview.链表;


/**
 * 输入两个单向链表，请问如何找出它们的第1个重合节点。
 * 例如，图4.5中的两个链表的第1个重合节点的值是4
 */
public class 寻找两个链表的第一个相交节点 {


    /**
     * 先找出较长的链表，然后长的链表先往后走两个链表相差的节点数的步数，短的链表指针都头节点开始，两个指针以
     * 相同的速度往下走，知道两个指针相遇，此时相遇的节点就是公共节点
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int count1 = countList(headA);
        int count2 = countList(headB);
        int delta = Math.abs(count1 - count2);
        ListNode longer = count1 > count2 ? headA : headB;
        ListNode shorter = count1 > count2 ? headB : headA;
        //拿到较长链表的头结点，先往后走delta步
        ListNode node1 = longer;
        for (int i = 0; i < delta; ++i) {
            node1 = node1.next;
        }
        ListNode node2 = shorter;
        //二者相遇就是公共节点
        while (node1 != node2) {
            node2 = node2.next;
            node1 = node1.next;
        }
        return node1;

    }






    /**
     * 找到一个单链表的长度
     *
     * @param head
     * @return
     */
    private int countList(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }




}
